MDN 怎麼定義

Arrays are list-like objects whose prototype has methods to perform traversal and mutation operations. Neither the length of a JavaScript array nor the types of its elements are fixed. Since an array's length can change at any time, and data can be stored at non-contiguous locations in the array.

上述描述可以知道幾個特性：

• List-like，似列表，數個元素排列成有限序列。
• 可以從第一個元素開始，遍歷整個元素。
• 元素內的資料可以修改。
• 元素內的資料型別不用一致。
• 非固定長度，可以在任何時間修改。
• 資料儲存的位置並不一定要相鄰。

是的，這些都是習以為常的基本知識。

從 C 的角度，該怎麼重新理解？

與 JS 不同之處在於：

• 元素內的資料型別要一致。
• 固定長度，宣告時就要決定好。

首先要知道的是，為什麼 Array 的設計是線性排列？在於記憶體的使用方式，宣告 Array 長度與型別，同時表示該 Array 將跟記憶體要求一個連續的區塊，好預留足夠的空間可以存放元素。目的是為了能夠有效運用記憶體而不浪費。

玩味的地方在於，因為 Array 的長度可能很長（意味著佔用大量的記憶體），所以使用 Array 時，傳遞該 Array 的記憶體位置（使用指標取得）遠比重新複製一個新 Array 來得快速許多，同時也能節省記憶體的消耗。這也就是為什麼 JS 中 Array 與 Object 會是 by reference，為了節省記憶體的消耗。

String

有了 C 的概念後，那 String 講白了就是宣告資料型別為字元的 Array 。因為長度固定，所以 C 在開發字串上蠻麻煩的。這點 Java 已經看出來，因此開發出 class String 來因應字串經常更改 Array 長度。

CRUD 相關操作

對於一位 JS 工程師而言，Array 的基本 CRUD 是必備的技能。這邊要提一點，部分內建函式對 Array 內的元素進行更動，此時要思考三點：

• 長度是否改變？長度增加時，可能記憶體區塊空間不足，要重新跟記憶體要求一塊，造成時間與資源的浪費。
• 元素的順序是否更動？最可怕的莫過於 Array.prototype.shift()，所有元素的 index 都會變更，肯定會造成記憶體的消耗。
• 菜雞時期喜歡用內建的 Array 函式，使用越多越覺得自己很厲害，一下 Array.prototype.map()、一下 Array.prototype.filter()，說穿了，都是 for-loop 的語法糖，使用上沒有對錯，端看需求。
  • 前端來說，現在流行 Immutable Data 好簡化控制介面上許許多多的狀態與資料，因此流行使用 Array.prototype.map()、Array.prototype.filter() 等製造出新的 Array 。
  • 後端來說，尤其強調效率的場合，建議減少內建 Array 函式的使用，盡可能 for-loop 完成。原因在於每一個 Array 內建函式幾乎都在跑 for-loop，減少使用增進效率。

刷題：11. Container With Most Water

題目

連結

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Related Topics: Array, Two Pointer

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

思考

首先觀察題目的圖片，思考中間的數字比兩側還大時，是不是有影響到？無法判斷的情況下點擊 Hint 1，可以得知題目沒有要思考這麼細，單純比較頭尾的高度後，再藉由頭尾之間的距離算出面積，最後比較哪一組的面積最大即可。

這邊最快速的做法是 Two Pointer，一種適合用在 Array 的解題技巧，粗略來講，遍歷 Array 時，除了從頭遞增，同時從尾巴遞減，頭尾互相計算、運作後，可以得到一個最終答案。詳細操作之後討論。

解題

JS

/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = (height) => {
    let max = 0, start = 0, end = height.length - 1;

    while (start < end) {
      let width = end - start;
      let high = 0;

      if (height[start] < height[end]) {
        high = height[start];
        start++;
      } else{
        high = height[end];
        end--;
      }

      let temp = width * high;

      if (temp > max) {
        max = temp;
      }
    }

    return max;
};

Java

class Solution {
    public int maxArea(int[] height) {
        int max = 0, start = 0, end = height.length - 1;

        while (start < end) {
            int width = end - start;
            int high = 0;

            if (height[start] < height[end]) {
                high = height[start];
                start++;
            } else {
                high = height[end];
                end--;
            }

            int temp = width * high;

            if (temp > max) {
                max = temp;
            }
        }

        return max;
    }
}

C

int maxArea(int *height, int heightSize)
{
    int max = 0, start = 0, end = heightSize - 1;

    while (start < end)
    {
        int width = end - start;
        int high = 0;

        if (height[start] < height[end])
        {
            high = height[start];
            start++;
        }
        else
        {
            high = height[end];
            end--;
        }

        int temp = width * high;

        if (temp > max)
        {
            max = temp;
        }
    }

    return max;
}

看法

這題個人歸類在腦經急轉彎的類型，想通後三種語言的實作皆十分相似。

結論

Array 是基本功中的基本功，JS 的工程師要補充 C 如何定義 Array 即可。至於其他解題技巧留在之後的文章內討論。